package com.zlk.algorithm.dataStructure.graph.shortestPath;

import org.junit.Test;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

// Dijkstra算法模版（Leetcode）
// 网络延迟时间
// 有 n 个网络节点，标记为 1 到 n
// 给你一个列表 times，表示信号经过 有向 边的传递时间
// times[i] = (ui, vi, wi)，表示从ui到vi传递信号的时间是wi
// 现在，从某个节点 s 发出一个信号
// 需要多久才能使所有节点都收到信号
// 如果不能使所有节点收到信号，返回 -1
// 其实就是计算到最远节点的最短路径和
// 测试链接 : https://leetcode.cn/problems/network-delay-time
public class Code01_DijkstraLeetcode {

    @Test
    public void test(){
        //[[2,1,1],[2,3,1],[3,4,1]]

        int[][] arr = new int[3][3];

        arr[0]=new int[]{2,1,1};
        arr[1]=new int[]{2,3,1};
        arr[2]=new int[]{3,4,1};
        System.out.println(networkDelayTime(arr, 4, 2));
    }


    /**
     * 前提无负权边
     * 1、构建树
     * 2、准备好变量  distance距离表   visit 是否访问表  heap （记录源点到当前点的距离）
     * 3、初始状态 distance 到所有点都是不可达，visit 都是false
     * 4、设置源点到源点距离为0，  将源点到当前点的边加入到heap
     * 5、弹堆，判断当前点是否访问过，有就继续弹堆，没有就设置visit为true，
     * 6、发散当前点的边，看能否跟新发散的点的距离，如果能更新距离并且没被访问，就距离加入堆中
     *
     * https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html 动画
     * 核心就是 先设置距离再弹堆。设置visit为ture之后就发散
     * 注意上述操作，先设置距离再设置visit。加入heap的前提是能将原来的距离更新的更小
     * @param times
     * @param n
     * @param k
     * @return
     */

    public int networkDelayTime(int[][] times, int n, int k) {
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        for (int i = 0; i<=n ; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < times.length; i++) {
            int from = times[i][0];
            int to = times[i][1];
            int w = times[i][2];
            graph.get(from).add(new int[]{to,w});
        }
        int[] distance = new int[n+1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        boolean[] isVisit = new boolean[n+1];
        // 记录源点到当前点的距离
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b)->a[1]-b[1]);
        distance[k]=0;
        heap.add(new int[]{k,0});
        while (!heap.isEmpty()){
            int[] poll = heap.poll();
            int cur = poll[0];
            int curWeight = poll[1];
            if(isVisit[cur]){
                continue;
            }
            isVisit[cur] = true;
            for (int[] next : graph.get(cur)) {
                //如果能更新距离并且没被访问，就距离加入堆中
                int nextNode = next[0];
                int nextWeight = next[1];
                if(!isVisit[nextNode]&&distance[nextNode]>distance[cur]+nextWeight){
                    //先设置距离，再加入堆，再设置visit
                    distance[nextNode] = distance[cur]+nextWeight;
                    heap.add(new int[]{nextNode,distance[cur]+nextWeight});
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <=n ; i++) {
            if(distance[i]==Integer.MAX_VALUE){
                return -1;
            }
            ans = Math.max(ans,distance[i]);
        }
        return ans;
    }

}
